Internet users like to be kept up-to-date with what is going on. To this end, social networking sites such as Twitter and Facebook provide, to a user, a feed of status updates, posted photos, movie reviews, and so on generated by the user's friends. Content aggregators such as My Yahoo and iGoogle provide a customized web page aggregating feeds from multiple RSS sources. Similarly, news aggregators such as Digg and Reddit provide a feed of the latest stories on topics like “entertainment” and “technology”, while news sites such as CNN.com provide the ability to follow fine-grained topics like “health care debate”.
Near real-time content feeds are becoming a key feature of many popular web applications. Examples include user generated events on Twitter and Facebook, and news stories on particular topics on iGoogle and My Yahoo. Consequently, it is increasingly important for these web applications to be able to efficiently construct a web page showing the latest contents from a user's feed. Constructing such a feed must be fast so the web page loads quickly. However, the wide fan-out of contents (e.g., some sources have many followers) and high skew (e.g., fan-out and rates vary widely) make it difficult to scale such applications.